1. Field
The present invention relates to content addressable memories, and more specifically, to a content addressable memory having a multi-stage priority encoder for encoding multiple matches in a content addressable memory.
2. Brief Description of the Related Art
Priority encoders are electronic logic circuits that determine which of a number of inputs has the highest or lowest priority. Priority encoders are used in a variety of computer systems, as well as other applications. Priority encoders can be utilized in conjunction with content addressable memory (CAM), for example.
Modern communications systems transmit data over digital networks. System resources are finite, so allocation of those resources becomes necessary. For example, system capacity limitations may restrict the amount of data that can be transmitted by the network, or a user may wish to give priority to certain categories of data over others.
Practically all digital networks make use of some form of packet or block type data format to dynamically route data packets or blocks through the network. The data contained in the packets can be categorized in various ways, including type of packet, packet content, size, creation date, and urgency of delivery, for example. Depending on the purpose of the communications system and the preferences of the user, it may be necessary to limit or expand the amount of bandwidth to be allocated to a particular category of data.
Content addressable memories (CAMs) are used in communications systems as search engines for routing paths in data network routers and switches. The packets being routed can be viewed as belonging to a particular category. Typically, a CAM issues a single search result that is independent of a packet category. Consequently, it is necessary for the user to handle bandwidth allocation, for example, by discarding search results for certain categories. A significantly more efficient way of utilizing a CAM as a search engine is needed.
CAM can be used to perform fast address searches. For example, Internet routers often include a CAM for searching an address containing specified data. Thus, CAMs allow routers to perform high speed address searches to facilitate more efficient communication between computer systems over computer networks. Besides routers, CAMs are also utilized in such areas as databases, network adapters, image processing, voice recognition applications, and others.
In contrast to random access memory (RAM), which returns data in response to requests, CAM returns an address where the requested data is located. In a typical application, a CAM memory array generates a number of match signals on a match line in response to a request. The match signals are provided to a priority encoder to determine the address corresponding to the highest priority match. In a typical application, a priority encoder can determine the highest priority match from among 128K match inputs.
Referring to FIG. 1, a typical priority encoder 2 is illustrated. Priority encoder 2 includes a highest priority indicator (HPI) 4 and an address encoder 6. The operation of HPI 4 can be likened to a “thermometer” for determining which of the match results has the highest priority. Conventionally, match inputs from respective match lines in a CAM are applied to terminals IN0-IN5 of HPI 2. An ENABLE signal is provided. When multiple matches are encountered, the match line located on the lowest segment of the HPI is given the highest priority, by convention, as described further below. The match line that indicates a match on inputs IN0-IN5 and which has the highest priority will cause the lowest output terminal PO0-PO5 to change states, indicating a match.
As shown in FIG. 1, HPI 4 utilizes an arrangement of logic gates to determine which of the inputs has the highest priority. Each stage of HPI 4 includes an inverter, a NAND gate, and a NOR gate. A highest priority segment 10 includes inverter 12 which inverts the ENABLE signal, and supplies it to NOR gate 14. NOR gate 14 also receives a signal on match line input IN0. ENABLE is supplied to NAND gate 16, along with match line input IN0. The result from NOR gate 14 is supplied on output terminal PO0. Output terminal PO0 supplies the match signal from the highest priority stage to address encoder 6.
HPI 2 includes six priority stages, each stage having a successively lower priority. Thus, the signal from NAND gate 16 is supplied to the next logically lowest priority stage (physically higher on the “thermometer,” as shown in FIG. 1) formed similarly of inverter 22, NOR gate 24, and NAND gate 26. NOR gate 24 supplies a signal to output terminal PO1, and NAND gate 26 supplies its signal to the third lowest priority stage formed of inverter 32, NOR gate 34, and NAND gate 36. A similar fourth-lowest priority stage is shown which includes inverter 42, NOR gate 44, and NAND gate 46. A similar fifth-lowest priority stage is shown which includes inverters 52, NOR gate 54, and NAND gates 56, providing an output signal on PO4 to address encoder 6. A final sixth stage includes NOR gate 58, providing its output signal on PO5.
In operation, matches supplied from a CAM (not shown) are indicated on match lines IN0-IN6 as logic 0, the ENABLE signal having a logic 1. Thus, in the first stage, if match line IN0 is low, output PO0 will be high, indicating a highest priority match. If match lines IN1, IN2, and IN3 are active low, output PO1 will produce a high signal, indicating a highest priority match. The remaining output signals PO0 and PO2-PO5 will be logic low.
In certain applications, it may be desirable to encode more than one highest priority input. For example, in CAMs, the comparand data bits are implemented such that a comparison can be made for a logic state of 1, a logic state of 0, or a “don't care” state wherein bits in the comparand register are masked as not to be involved in the matching search, and a match is declared regardless of what state is in the respective “don't care” bits in the CAM words. These “don't care” bits are used typically in a search known in the art as a search for the longest match. As a result of a search for the longest match, multiple words in the CAM may match the un-masked data bits in the comparand register. In such typical application, a special multi-match detection circuit indicates the presence of multiple matches. Using a typical prior art priority encoder, only one match, the one with the highest priority, is recorded. It is desirable, instead, to find the identity of all the matching words. In order to determine the next highest priority match, the user must discard the highest priority match, and re-encode the CAM match results to obtain the next highest priority match. Such manual manipulation of the CAM results is time consuming and inefficient.
A priority encoder is needed that can encode multiple matches in a CAM.